本文中的课件来自清华大学深圳国际研究生院，物流与交通学部戚铭尧教授《物流地理信息系统》课程。

  带资源约束的最短路径问题（shortest path problem with resource constraints）是一个众所周知的NP-Hard问题。 除了作为网络问题直接应用外，SPPRC还用作列生成解决方案方法的基础，用于解决车辆路径规划问题和人员排班问题等。 　　考虑一个有向图 G = ( N , A ) G = (N,A) G=(N,A)， N = { v 1 , v 2 , . . . , v i , . . . , v n } N=\{v_1,v_2,...,v_i,...,v_n\} N={v1​,v2​,...,vi​,...,vn​}表示节点的集合，并且 A = { ( i , j ) ∣ v i ∈ N , v j ∈ N , i ≠ j } A=\{(i,j)|v_i \in N,v_j \in N ,i \ne j\} A={(i,j)∣vi​∈N,vj​∈N,i​=j}表示弧的集合。对于每一段弧 ( i , j ) ∈ A (i,j)\in A (i,j)∈A都有一个非负的权重(vrptw问题中可能为负，需要作特殊处理)， c i j c_{ij} cij​和 t i j t_{ij} tij​，表示通过这段弧的成本和资源消耗。 　　SPPRC问题包括找到从起始节点 v s ∈ N v_s \in N vs​∈N到结束节点 v t ∈ N v_t \in N vt​∈N的一条路径 P P P，使该路径的总成本最小化，但不超过最大资源消耗 T T T。即使只存在一种资源，SPPRC也是一个NP-Hard。

  直接求解SPPRC问题是比较困难的，故通常采用一种动态规划的方法： l a b e l   c o r r e c t i o n   a l g o r i t h m label \ correction \ algorithm label correction algorithm算法。 通常我们考虑有 L L L种资源，可能包括时间、最大装载重量、最大装载体积等。   对于每一条从起始节点 v s v_s vs​扩展到点 v i v_i vi​的路径 X p i X_{pi} Xpi​都有一个标签 ( R i , C i ) (R_i,C_i) (Ri​,Ci​)与之相关联。 R i ≡ ( T i 1 , T i 2 , . . . , T i L ) R_i \equiv (T_i^1,T_i^2,...,T_i^ L) Ri​≡(Ti1​,Ti2​,...,TiL​)是路径使用的每L个资源的数量； C i C_i Ci​是 c o s t cost cost。   此外，我们还需要设置一些优超规则，称为 d o m i n a n c e   r u l e dominance\ rule dominance rule，以帮助减少不必要的扩展。令 X p i X_{pi} Xpi​和 X p i ∗ X_{pi}^* Xpi∗​是从 v s v_s vs​扩展到 v i v_i vi​的两条不同的路径，与之关联的标签分别为 ( R i , C i ) (R_i,C_i) (Ri​,Ci​)和 ( R i ∗ , C i ∗ ) (R_i^*,C_i^*) (Ri∗​,Ci∗​)。路径 X p i X_{pi} Xpi​可以 d o m i n a t e s dominates dominates路径 X p i ∗ X_{pi}^* Xpi∗​当且仅当： C i ≤ C i ∗ , T i l ≤ T i l ∗ , ∀   l ∈ ( 1 , . . . , L ) , ( R i , C i ) ≠ ( R i ∗ , C i ∗ ) C_i \le C_i^*,T_i^l\le T_i^{l*} ,\forall \ l \in (1,...,L), (R_i,C_i) \ne (R_i^*,C_i^*) Ci​≤Ci∗​,Til​≤Til∗​,∀ l∈(1,...,L),(Ri​,Ci​)​=(Ri∗​,Ci∗​)

下面介绍一个简单的小例子： 一个有向图如上图所示，我们可以看到每一段弧上都有一个非负的权重，分别表示通过该弧的 t i m e time time与 c o s t cost cost。首先初始化出发节点 p p p的标签，设置为 [ 0 , 0 ] [0,0] [0,0]，随后令其向可达节点 v 2 v_2 v2​和 v 3 v_3 v3​进行扩展，则分别设置一个新的标签 [ 2 , 2 ] [2,2] [2,2]。再由 v 2 v_2 v2​向 v 3 v_3 v3​和 d d d进行扩展，则 v 3 v_3 v3​得到一个新的标签 [ 3 , 0 ] [3,0] [3,0]， d d d得到一个新的标签 [ 4 , 4 ] [4,4] [4,4]，同理继续扩展到 d d d，生成一个新的标签 [ 5 , 2 ] [5,2] [5,2]。然后回过头由 v 3 v_3 v3​扩展到 v 2 v_2 v2​， v 2 v_2 v2​得到一个新的标签 [ 4 , 1 ] [4,1] [4,1]。我们可以发现没有继续向 d d d扩展了，因为其生成的标签为 [ 6 , 2 ] [6,2] [6,2]，与 d d d已有的标签 [ 5 , 2 ] [5,2] [5,2]相比满足了 d o m i n a n c e   r u l e dominance\ rule dominance rule的要求，不必再扩展。

考虑这样一个有向图。